class LRUCache:

    def __init__(self, capacity: int):
        self.capacity=capacity
        self.dictionary=dict()
        self.dictKeys=[]  #记录存储的key
        self.useinfoQueue=[]  #做一个队列，用来记录key的情况

    def get(self, key: int) -> int:
        #返回对应key的值，如果key不在字典中，就返回-1
        if key in self.dictKeys:
            #使用了当前的Key-value
            #把这个键值对放到队列的尾部去
            self.useinfoQueue.remove(key)
            self.useinfoQueue.append(key)
            return self.dictionary[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        # dictKeys=self.dictionary.keys()
        if key in self.dictKeys:
            #键已经存在于字典中了
            self.dictionary[key]=value
            #将其key从queue中先移除掉，然后插入到队列的尾部
            self.useinfoQueue.remove(key)
            self.useinfoQueue.append(key)
        else:
            if len(self.dictionary)==self.capacity:
                #已经满了
                #删掉队列中的第一个元素key值
                delKey=self.useinfoQueue.pop(0)
                del self.dictionary[delKey]
            # 将新的key-value加入到字典中，并把key加入到队列的尾部
            self.dictionary[key] = value
            self.useinfoQueue.append(key)
            self.dictKeys=self.dictionary.keys()
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)